package com.hanxiaozhang.link.doublelink;

import com.hanxiaozhang.util.AlgorithmUtil;

/**
 * 〈一句话功能简述〉<br>
 * 〈双向链表〉
 *
 * @author hanxinghua
 * @create 2021/9/5
 * @since 1.0.0
 */
public class DoubleLink {

    public static void main(String[] args) {

//        // # 头节点
//        DoubleNode<Integer> head = new DoubleNode<>(3);
//        whileNode(head);
//        // # 插入
//        // -- head节点之后插入
//        head = addOnAfter(head, 5);
//        whileNode(head);
//        // -- head.next节点之前插入
//        head = addOnBefore(head, 4);
//        whileNode(head);
//        // # 删除 head.next节点
//        head = remove(head);
//        whileNode(head);


        DoubleNode head = AlgorithmUtil.generateRandomDoubleLinked(4, 10);
        whileNode(head);
        head = reverse(head);
        whileNode(head);

    }


    /**
     * 节点之后添加
     *
     * @param head
     * @param data
     * @return
     */
    private static DoubleNode addOnAfter(DoubleNode<Integer> head, int data) {

        DoubleNode node = new DoubleNode(data, head, head.next);
        if (head.next != null) {
            head.next.pre = node;
        }
        head.next = node;
        return head;
    }

    /**
     * head.next节点之前插入
     *
     * @param head
     * @param data
     * @return
     */
    private static DoubleNode addOnBefore(DoubleNode<Integer> head, int data) {

        DoubleNode<Integer> target = head.next;
        DoubleNode node = new DoubleNode(data, target.pre, target);
        target.pre.next = node;
        target.pre = node;
        return head;
    }


    /**
     * 删除 head.next节点
     *
     * @param head
     * @return
     */
    private static DoubleNode<Integer> remove(DoubleNode<Integer> head) {
        DoubleNode<Integer> target = head.next;
        target.pre.next = target.next;
        if (target.next != null) {
            target.next.pre = target.pre;
        }
        return head;
    }

    /**
     * 循环打印
     *
     * @param head
     */
    public static void whileNode(DoubleNode head) {
        System.out.println("----------");
        while (head != null) {
            System.out.println(head.data);
            head = head.next;
        }
    }

    /**
     * 翻转
     * 思路是，从head的后继节点开始，把指针指向前继
     *
     * @param head
     * @return
     */
    public static DoubleNode reverse(DoubleNode head) {

        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            // 两个指针方向翻转
            head.next = pre;
            head.pre = next;
            // head节点变成前继节点
            pre = head;
            // next节点变成head节点
            head = next;
        }
        return pre;
    }
}
